package com.leetcode.根据数据结构分类.二叉树;

import com.leetcode.datastructure.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author: ZhouBert
 * @date: 2020/12/17
 * @description: 101. 对称二叉树
 * https://leetcode-cn.com/problems/symmetric-tree/
 */
public class A_101_对称二叉树 {

	/**
	 * 感觉就是将 root 的 left 和 right 分别进行【层序遍历】和 【逆层序遍历】
	 * 迭代版本（其实就是层序遍历的修改版本，站在层序遍历的肩膀上！）
	 * @param root
	 * @return
	 */
	public boolean isSymmetricByIterator(TreeNode root) {
		if (root == null) {
			return true;
		}
		TreeNode curLeft = root.left;
		TreeNode curRight = root.right;
		Queue<TreeNode> leftQueue = new LinkedList<>();
		if (curLeft != null) {
			leftQueue.offer(curLeft);
		}

		Queue<TreeNode> rightQueue = new LinkedList<>();
		if (curRight != null) {
			rightQueue.offer(curRight);
		}

		//再每一次循环里，都只做一次比较！
		while (!leftQueue.isEmpty() && !rightQueue.isEmpty()) {
			curLeft = leftQueue.poll();
			curRight = rightQueue.poll();
			if (curLeft.val != curRight.val) {
				return false;
			}

			if (curLeft.left != null && curRight.right != null) {
				leftQueue.offer(curLeft.left);
				rightQueue.offer(curRight.right);
			} else if (curLeft.left == null && curRight.right == null) {

			} else {
				return false;
			}
			if (curLeft.right != null && curRight.left != null) {
				leftQueue.offer(curLeft.right);
				rightQueue.offer(curRight.left);
			} else if (curLeft.right == null && curRight.left == null) {

			} else {
				return false;
			}
		}
		if (leftQueue.isEmpty() && rightQueue.isEmpty()) {
			return true;
		} else {
			return false;
		}
	}

	/**
	 * 通过递归进行解决
	 * 分析：
	 * 假设有个方法，
	 *
	 */
	public void isSymmetricByRecursive(){

	}

	public static void main(String[] args) {
		String str = "[1,2,2,3,4,4,3]";
		str = "[1,0]";
		str = "[1,2,2,3,4,4,3]";
		TreeNode root = TreeNode.stringToTreeNode(str);
		A_101_对称二叉树 action = new A_101_对称二叉树();
		boolean symmetric = action.isSymmetricByIterator(root);
		System.out.println("symmetric = " + symmetric);
	}
}
